#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>


struct TreeNode 
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};


struct TreeNode* invertTree(struct TreeNode* root)
{
    if (root == NULL)
        return NULL;
    SwapTree(root);
    return root;
}


void SwapTree(struct TreeNode* root)
{
    if (root == NULL)
        return;
    struct TreeNode* left = root->left;
    root->left = root->right;
    root->right = left;
    SwapTree(root->left);
    SwapTree(root->right);
}

int preorderCount(struct TreeNode* root)
{
    if (root == NULL)
        return 0;
    return 1 + preorderCount(root->left) + preorderCount(root->right);
}

void preorder(struct TreeNode* root, int* tmp, int* result)
{
    if (root == NULL)
        return;
    result[*tmp] = root->val;
    (*tmp)++;
    preorder(root->left, tmp, result);
    preorder(root->right, tmp, result);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = preorderCount(root);
    int* result = (int*)malloc(sizeof(int) * (*returnSize));
    int tmp = 0;
    preorder(root, &tmp, result);
    return result;
}


bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
        return true;
    if (p == NULL || q == NULL)
        return false;
    return p->val == q->val 
        && isSameTree(p->left, q->right) 
        && isSameTree(p->right, q->left);
}


bool isSymmetric(struct TreeNode* root) 
{
    return isSameTree(root->left, root->right);
}

bool isSameTree(struct TreeNode* rootleft, struct TreeNode* rootright)
{
    if (rootright == NULL && rootleft == NULL)
        return true;
    if (rootright == NULL || rootleft == NULL)
        return false;
    return rootleft->val == rootright->val &&
        isSameTree(rootleft->left, rootright->left) &&
        isSameTree(rootleft->right, rootright->right);


}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (subRoot == NULL)
        return true;
    if (root == NULL)
        return false;
    return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

int main()
{
	return 0;
}